package 单调栈;

import java.util.Stack;

public class LeetCode456_132模式 {
    /**
     * 单调栈维护的是3，max_k维护的是2，枚举的是1， max_k来源与单调栈，所以其索引一定大于栈顶的元素，
     * 但其值一定小于栈顶元素，故栈顶元素就是3，即找到了对“32”。 于是当出现nums[i] < max_k时，即找到了"12"，
     * 这个时候一定会有3个元素的，而栈顶3必定大于2，故也大于1，即满足“132”
     */
    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack = new Stack<Integer>();
        int length = nums.length;
        if(length < 3) {
            return false;
        }
        // maxK维护2
        int maxK = Integer.MIN_VALUE;

        // 枚举维护1，
        for(int i = length - 1; i >= 0; i--) {

            if(nums[i] < maxK) { // ② 再往前走，后面进去while了，32就维护好了，这里，满足if就维护了 12
                return true;
            }
            //
            while(!stack.isEmpty() && stack.peek() < nums[i]) {
                // ① 这里保证2一直小于3，并且i从后向前走，满足i<k。  维护了32
                maxK = stack.pop();
            }
            // 单调栈维护3
            stack.push(nums[i]);
        }
        return false;
    }
}
